package com.lbx.algo.linkedlist;

/**
 * 1）单链表的插入、删除、查找操作；
 * 2）链表中存储的是int类型的数据；
 * <p>
 * Author：Lbx
 */
public class SinglyLinkedList {

    private Node head;

    private void insertHead(Node newNode) {
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    private void insertHead(int value) {
        Node newNode = new Node(value, null);
        insertHead(newNode);
    }

    //顺序插入
    //链表尾部插入
    private void insertTail(int value) {
        Node newNode = new Node(value, null);
        if (head == null) {
            head = newNode;
        } else {
            Node p = head;
            while (p.next != null) {
               p = p.next;
            }
//            newNode.next = p.next;
            p.next = newNode;
        }
    }
    public void insertAfter(Node p, int value) {

        Node newNode = new Node(value, null);
        insertAfter(p,newNode);
    }

    public void insertAfter(Node p, Node newNode) {
        if(p == null){
            return;
        }
        newNode.next = p.next;
        p.next = newNode;
    }

    public void insertBefore(Node p, int value) {
        Node newNode = new Node(value, null);
        insertBefore(p, newNode);
    }

    public void insertBefore(Node p, Node newNode) {
        if(p == null){
            return;
        }
        if(head == p){
            insertHead(newNode);
        }
        Node q = head;
        while (q != null && q.next != p){
            q = q.next;
        }
        newNode.next = p;
        q.next = newNode;
    }

    public void deleteByNode(Node p) {
        if(p == null || head == null){
            return;
        }
        Node q = head;
        while (q != null && q.next != p){
            q = q.next;
        }
        q.next = p.next;
    }

    private void delete(int value) {
        if(head == null) return;
        Node p = head;
        Node q = null;
        while (p != null && p.data != value){
            q = p;
            p = p.next;
        }
        if (p == null) return;
        if(q == null){
            head = head.next;
        }else{
          q.next = q.next.next;
        }

    }

    private int get(int value) {
        return 0;
    }

    public static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }

    public void printAll() {
        Node p = head;
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SinglyLinkedList link = new SinglyLinkedList();
        int data[] = {1,2,5,3,1};
        for(int i =0; i < data.length; i++){
            //link.insertToHead(data[i]);
            link.insertTail(data[i]);
        }
        link.printAll();

        link.delete(2);
        link.printAll();
        link.insertHead(new Node(34,null));
        link.printAll();
        link.insertHead(21);
        link.printAll();
    }
}
